package de.tum.wi.som.prio.impl;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

import de.tum.wi.som.Node;
import de.tum.wi.som.Project;
import de.tum.wi.som.prio.PriorityRule;
import de.tum.wi.som.util.PrioUtil;

/**
 * Min(LSi–Max[E(i,j)|(i,j) e(APt)]), where E(i,j) is the earliest time to
 * schedule activity j if activity i is started at time t, and APt is the set of
 * all feasible pairs of eligible, un-started activities at time t
 * 
 * @author enricopollok
 * 
 */
public class MinimumWorstCaseSlack implements PriorityRule {

	@Override
	public void prioritize(Project project) {
		project.calcProjectGraph();
		Node[] nodes = project.getNodes();
		Node source = project.getSource();
		int[] resources = project.getR();

		List<Node> remainingNodes = new ArrayList<Node>();
		remainingNodes.addAll(Arrays.asList(nodes));
		List<Node> scheduledNodes = new ArrayList<Node>();
		List<Node> accessibleNodes;

		double t = 0;
		double tMin = Double.POSITIVE_INFINITY;
		double e = 0;
		Map<Node, Set<Node>> eligibleUnstarted;
		Node dummyNode = new Node(0, new int[0]);
		Node candidateNode = dummyNode;
		while (!remainingNodes.isEmpty()) {
			accessibleNodes = PrioUtil.determineAccesibleNodes(scheduledNodes,
					source, remainingNodes);
			if (accessibleNodes.size() == 0) {
				System.err
						.println("No accessible nodes found in MinimumWorstCaseSlack");
				return;
			}
			// reset variables
			tMin = Double.POSITIVE_INFINITY;
			e = 0;
			candidateNode = dummyNode;
			eligibleUnstarted = computeEligibleUnstarted(resources,
					accessibleNodes);
			// for all node pairs i, j in eligibleUnstarted, take the node with
			// maximum of the earliest possible schedule time
			for (Node i : eligibleUnstarted.keySet()) {
				Set<Node> nodeSet = eligibleUnstarted.get(i);
				for (Node j : nodeSet) {
					if (accessibleNodes.contains(j)) {
						if (t + i.getD() > e) {
							e = t + i.getD();
						}
					} else {
						double est;
						if ((est = getEarliestSchedulableTime(i, j)) > e) {
							e = est;
						}
					}
				}
				if (i.getLatestStart() - e < tMin) {
					tMin = i.getLatestStart() - e;
					candidateNode = i;
				}
			}
			if (candidateNode != dummyNode) {
				scheduledNodes.add(candidateNode);
				remainingNodes.remove(candidateNode);
			} else {
				throw new RuntimeException("Could not find next node for MWCS");
			}
		}

		project.setNodes(scheduledNodes.toArray(new Node[scheduledNodes.size()]));
	}

	private double getEarliestSchedulableTime(Node i, Node j) {
		// earliest schedulable time is the maximum of the earliestStartTimes of
		// all predecessors
		double t = 0;
		for (Node iPredecessor : i.getPredecessors()) {
			if (iPredecessor.getEarliestStart() > t)
				t = iPredecessor.getEarliestStart();
		}

		for (Node jPredecessor : j.getPredecessors()) {
			if (jPredecessor.getEarliestStart() > t)
				t = jPredecessor.getEarliestStart();
		}
		return t;

	}

	private Map<Node, Set<Node>> computeEligibleUnstarted(
			int[] availableResources, List<Node> remainingNodes) {
		Map<Node, Set<Node>> eligibleUnstarted = new HashMap<Node, Set<Node>>();
		List<Node> remainingNodesCopy = new ArrayList<Node>();
		remainingNodesCopy.addAll(remainingNodes);

		// take all pairs of nodes i and j, who fulfill the resource constraints
		// when scheduled in parallel
		for (Node i : remainingNodes) {
			Set<Node> nodeSetI = new HashSet<Node>();
			for (Node j : remainingNodesCopy) {
				if (i != j
						&& isResourceFeasible(availableResources, i.getR(),
								j.getR()))
					nodeSetI.add(j);
			}
			eligibleUnstarted.put(i, nodeSetI);
		}

		return eligibleUnstarted;
	}

	private boolean isResourceFeasible(int[] totalResources,
			int[] resourceConsumptionActivity1,
			int[] resourceConsumptionActivity2) {
		if (totalResources.length != resourceConsumptionActivity1.length
				|| resourceConsumptionActivity1.length != resourceConsumptionActivity2.length) {
			throw new RuntimeException(
					"Error computing isResourceFeasible: numberOfResources is not equal.");
		}
		for (int i = 0; i < totalResources.length; i++) {
			if (resourceConsumptionActivity1[i]
					+ resourceConsumptionActivity2[i] > totalResources[i])
				return false;
		}
		return true;
	}

	@Override
	public String toString() {
		return "MinimumWorstCaseSlack";
	}
}
